#include "queue.h"

// 1.建立图的邻接表结构.
// n个节点，e条边.
// 时间复杂度：O(n + e).
void CreateALGraph(GraphAdjList *G)
{
	int i, j, k;
	EdgeNode *e;
	// 输入顶点数和边数.
	printf("请输入顶点数和边数：\n");
	scanf("%d%d", &G->numVertexes, &G->numEdges);
	// 建立顶点表.
	printf("请输入顶点的值：\n");
	for (i = 0; i < G->numVertexes; i++) {
		scanf("%d", &G->adjList[i].val);
		G->adjList[i].firstedge = NULL;
	}
	// 建立边表.
	for (k = 0; k < G->numEdges; k++) {
		printf("请输入边(vi, vj)上的顶点序号:\n");
		scanf("%d%d", &i, &j);
		// 头插法建立边表.
		e = (EdgeNode *)malloc(sizeof(EdgeNode));
		e->adjvex = j;
		e->next = G->adjList[i].firstedge;
		G->adjList[i].firstedge = e;
		/*
		// 无向图，所以要重复一次，互相有一条弧.
		e = (EdgeNode *)malloc(sizeof(EdgeNode));
		e->adjvex = i;
		e->next = G->adjList[j].firstedge;
		G->adjList[j].firstedge = e;
		*/
	}
}

void BFSTraverse(GraphAdjList *GL)
{
	int i;
	EdgeNode *p;
	LinkQueue Q;
	for (i = 0; i < GL->numVertexes; i++) {
		visited[i] = false;
	}
	Q = createEmptyQueue_link();
	for (i = 0; i < GL->numVertexes; i++) {
		if (!visited[i]) {
			visited[i] = true;
			printf("%d ", GL->adjList[i].val);
			enQueue_link(Q, i);
			while (!isEmptyQueue_link(Q)) {
				i = frontQueue_link(Q);
				deQueue_link(Q);
				p = GL->adjList[i].firstedge;
				while (p) {
					if (!visited[p->adjvex]) {
						visited[p->adjvex] = true;
						printf("%d ", GL->adjList[p->adjvex].val);
						enQueue_link(Q, p->adjvex);
					}
					p = p->next;
				}
			}
		}
	}
}

int main()
{
	GraphAdjList G;
	CreateALGraph(&G);
	printf("邻接表的广度优先遍历为：\n");
	BFSTraverse(&G);
	printf("\n");
	return 0;
}
